파이썬으로 문자열 썰고 붙이고 딕셔너리 뒤지고 붙이고 느려서 그냥 고랭을 한 두시간 좀 봤는데 문자열 다루기가 편한 것 같다.
배열을 보니까 큐 같은 걸 배열로 구현한 글들을 본다. 마침 고랭의 배열 슬라이싱을 테스트해보니 당연히 레퍼런싱이다. 즉, 배열을 슬라이싱해다가 쓴 것은 레퍼런스 메타일 뿐 복제가 일어나지 않는다. 당연한 것이고 이래야 속도가 빠르다.
연장선상의 컨셉으로 append를 하면 capacity에 이르러 복제 후 재할당을 한다. c에서 realloc 할 때랑 비슷한 거다. 만약 무진장 길어질 수도 있는 LIFO 큐가 있다고 치자. 이 큐를 return q[0], q = q[1:] 방식으로 구현하면 온당한가? 슬라이싱 자체는 비용을 먹지 않으니 안심. 그러나 capacity에 이르러 자기복제가 일어나고, de큐는 간헐적으로 대량, en큐는 상시 고부하라고 상정하면 realloc 한다고 상시 뻐덕뻐덕 할 것이다. en큐가 간헐적으로 대량이면 그 때만 쑈하면 되니까 프론트 밀접 시스템이 아니면 괜찮다.
즉, 대용량 큐라면 리스트를 써야 한다는 거다. 물론 캐시 힛팅이 빠개지고 CPU 파이프가 다 깨지고 손해는 보겠지만 고랭 만든 사람들이 알아서 잘 만들었을 거. 보통 벡터도 그렇고 malloc류도 그렇고 통계적으로 자주 쓰는 청크 단위로 한 방에 여유 블록을 구성해두면 그 구간에 있어서 캐시도 파이프도 덜 깨진다. STL도 그리 만든 걸로 알고 있다. 여튼 고랭의 창조자들 이름은 까먹었지만 전설들이라고 하고 멤버에 대머리가 있는 것이 보나마나 천재들이 만들었음.